﻿namespace LeetCodeProject._0001_1000._001_100._21_30._028;

public class Solution
{
    public int StrStr(string haystack, string needle)
    {
        if (string.IsNullOrEmpty(needle))
            return 0;
        if (string.IsNullOrEmpty(haystack))
            return -1;
        return sandy(haystack, needle);
    }

    private int sandy(string s, string p)
    {
        var shift = new Dictionary<char, int>(p.Length);
        for (int i = 0; i < p.Length; i++)
        {
            shift[p[i]] = p.Length - i;
        }

        var left = 0;
        while (left <= s.Length - p.Length)
        {
            var matched = true;
            for (int j = 0; j < p.Length; j++)
            {
                if (s[left + j] != p[j])
                {
                    matched = false;
                    break;
                }
            }

            if (matched)
                return left;
            if (left + p.Length < s.Length && shift.TryGetValue(s[left + p.Length], out var n))
            {
                left += n;
            }
            else
            {
                left += p.Length + 1;
            }
        }

        return -1;
    }
}